字符串的贡献在第一个位置，为了与 $\text{endpos}$ 对应上考虑将串翻转。

两杯酒 $p,q$ 的最大相似度就是 $\text{lcp}(p,q)$ ，即后缀自动机 $\text{parent}$ 树上 $last_p,last_q$ 两个节点的 $\text{lca}$。

大的相似度会对较小的相似度产生影响，可以看作在后缀树上从深度大的节点考虑。

$\sum_{1\leqslant i <j\leqslant n}\text{len}(T_i)+\text{len}(T_j)-2\times\text{lcp}(T_i,T_j)$

$\left(\sum_{1\leqslant i <j\leqslant n}\text{len}(T_i)+\text{len}(T_j)\right)-2\sum_{1\leqslant i <j\leqslant n}\text{lcp}(T_i,T_j)$

$\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m \mu(\text{lcm}(i,j)) \\$

由题显然有：

$\begin{cases}$

$\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)^{i+j}$

$\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]d^{i+j}$

记 $c_i$ 为 $i$ 毫升泡沫的酒在架子上的瓶数，$A=\max_{i=1}^n a_i$。

为了方便将二元组视为有序，答案除以 $2$ 即可。

$\sum_{i=1}^A \sum_{j=1}^A c_i c_j [\gcd(i,j)=1]$

建议先做 CF439E。

$\sum_{n=1}^y\sum_{i_1=1}^y\sum_{i_2=1}^y...\sum_{i_n=1}^y [\sum{a_i}=y][\gcd{a_i}=x]$

$\sum_{i_1=1}^n\sum_{i_2=1}^n...\sum_{i_f=1}^n [\sum{a_i}=n][\gcd{a_i}=1]$

$\sum_{i_1=1}^n\sum_{i_2=1}^n...\sum_{i_f=1}^n [\sum{a_i}=n]\sum_{d|\gcd{a_i}} \mu(d)$

给出一个易于理解且好写的做法。

有一个贪心做法，

阅读全文 »

注意本篇题解的 $k$ 是题目中的 $d$。

$\sum_{i=1}^n[\gcd(i,n)=1]i^k$